package dfs_bfs.test77;

import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.List;

/**
 * 组合
 * @author code_yc
 * @version 1.0
 * @date 2020/7/8 13:59
 */
public class Solution1 {

    // DFS 深度优先遍历
    List<List<Integer>> ans = new ArrayList<>();

    public List<List<Integer>> combine(int n, int k) {
        if (n < k || k == 0) return ans;
        dfs(n, k, 1, new ArrayDeque<Integer>());
        return ans;
    }

    // dfs
    private void dfs(int n, int k, int c, ArrayDeque<Integer> path) {
        if (path.size() == k) {
            ans.add(new ArrayList<>(path));
            return;
        }
        for (int i = c; i <= n; i++) {
            path.addLast(i);
            dfs(n, k, i + 1, path);
            path.removeLast();
        }
    }
}
